//Creates (first) derivative of the tree - builds new tree.
#include "Multitree.h"
#include "Diff.h"
#include <string.h>
#include <gc/gc.h>


Multitree * diff_tree(Multitree * tree, char * variable){

	/*Creates first derivative of the tree using standard rules.
	Derivative of a*b*c*... is sum a'*b*c*...+a*b'*c*...+a*b*c'*....+...
	Derivative of 1/b is -1*b'/b^2 (that needs a huge tree...)*/
	Multitree * to_return = NULL;
	/*Helpful constants. use: Multitree * something = copy_tree(&constant); - probably should  have been pointers too*/
	Multitree zero;
	Multitree one;
	Multitree minusone;
	Number * numberzero;

	Multitree * argument = NULL;
	Multitree * dargument=NULL; 
	Multitree * cosin = NULL;
	Multitree * two = NULL;
	Multitree * sinus = NULL;
	Multitree * pow = NULL;
	Multitree * tmp = NULL;
	numberzero = construct_number();


	inttonum(numberzero, 0);
	zero.symbol.number = construct_number();
	zero.childs = NULL;
	zero.symbol.type = NUMBER;

	numbercpy(zero.symbol.number, numberzero);

	one.childs = NULL;
	one.symbol.type = NUMBER;
	one.symbol.number = construct_number();
	inttonum(one.symbol.number, 1);
	
	minusone.childs = NULL;
	minusone.symbol.type = NUMBER;
	minusone.symbol.number = construct_number();
	inttonum(minusone.symbol.number, -1);
	if(tree == NULL){
		return NULL;
	}

	switch(tree->symbol.type){
		case NUMBER:
		case CONSTANT:
			/*return zero.*/
			return copy_tree(&zero);
			break;

		case VARIABLE:
			if (strcmp(tree->symbol.name, variable) == 0){
				return copy_tree(&one);
			}else{
				return copy_tree(&zero);
			}
			break;

		case FUNCTION:
			dargument = diff_tree(tree->childs->subtree, variable);
			if (dargument == NULL){
				return NULL;
			}
			if ((dargument->symbol.type == NUMBER)
				&& (numbercmp(dargument->symbol.number, numberzero) == 0)){
					GC_FREE(dargument);
					return copy_tree(&zero);
					/*why not return dargument?*/
			}
			/*dargument is ot zero. So we have to differentiate the function.*/
			argument = tree->childs->subtree; /*copy it. It is just name.*/
			/*f(x)' = x'*f'(x). x' is dargument, x is argument. to_return is * in between.*/
			to_return = give_me_empty_tree();
			to_return->symbol.type = OPERATOR;
			to_return->symbol.oper = MULTIPLY;
			to_return->childs = give_me_empty_child();
			to_return->childs->inverted = 0;
			to_return->childs->next = NULL;
			to_return->childs->subtree = dargument;
			/*to_return is dargument*(NULL). Now replace NULL with derivative of function.*/

			switch (tree->symbol.func){
				case SIN:
					cosin = give_me_empty_tree();
					cosin->symbol.type = FUNCTION;
					cosin->symbol.func = COS;
					cosin->childs = give_me_empty_child();
					cosin->childs->inverted = 0;
					cosin->childs->next = NULL;
					cosin->childs->subtree = copy_tree(argument);
					to_return->childs->next=give_me_empty_child();
					to_return->childs->next->inverted = 0;
					to_return->childs->next->next=NULL;
					to_return->childs->next->subtree = cosin;
					break;
				case COS:
					/*derivative of cos is -sin.
					So add to to_return sin(a) and then add there -1.
					create sin(argument)*/
					sinus = give_me_empty_tree();
					sinus->symbol.type = FUNCTION;
					sinus->symbol.func = SIN;
					sinus->childs = give_me_empty_child();
					sinus->childs->inverted = 0;
					sinus->childs->next = NULL;
					sinus->childs->subtree = copy_tree(argument);
					to_return->childs->next = give_me_empty_child();
					to_return->childs->next->inverted = 0;
					to_return->childs->next->subtree = sinus;
					to_return->childs->next->next = give_me_empty_child(); /*here we put minus one.*/
					to_return->childs->next->next->next = NULL;
					to_return->childs->next->next->inverted = 0;
					to_return->childs->next->next->subtree = copy_tree(&minusone);
					sort_tree(to_return);
					break;
					/*der. of cos is -sin. So second child of to_return will be 0-cos(argument).
					
					minus = new Multitree;
					minus->symbol.type = OPERATOR;
					minus->symbol.oper = PLUS;
					minus->childs = new ListOfChilds;
					minus->childs->next = new ListOfChilds;
					minus->childs->next->inverted = true;
					minus->childs->next->next = NULL;
					minus->childs->next->subtree = copy_tree(argument);
					minus->childs->inverted = false;
					minus->childs->subtree = copy_tree(&zero);
					//minus is 0-argument.
					to_return->childs->next = new ListOfChilds;
					to_return->childs->next->next = NULL;
					to_return->childs->next->subtree = minus;
					to_return->childs->next->inverted = false;
					break;
					*/
				case LN:
					/*deriv. of ln(x) is x'/x.*/
					to_return->childs->next = give_me_empty_child();
					to_return->childs->next->next = NULL;
					to_return->childs->next->inverted = 1; //this is / in x'/x
					to_return->childs->next->subtree = copy_tree(argument);
					break;
				case TAN:
					/*tan(a)' = a'/cos(a)^2*/
					cosin = give_me_empty_tree();
					cosin->symbol.type = FUNCTION;
					cosin->symbol.func = COS;
					cosin->childs = give_me_empty_child();
					cosin->childs->next = NULL;
					cosin->childs->inverted = 0;
					cosin->childs->subtree = copy_tree(argument);
					two = inttotree(2);
					pow = give_me_empty_tree();
					pow->symbol.type = OPERATOR;
					pow->symbol.oper = POWER;
					pow->childs = give_me_empty_child();
					pow->childs->next = give_me_empty_child();
					pow->childs->next->next = NULL;
					pow->childs->next->inverted = 0;
					pow->childs->next->subtree = two;
					pow->childs->inverted = 0;
					pow->childs->subtree = cosin;
					to_return->childs->next = give_me_empty_child();
					to_return->childs->next->next = NULL;
					to_return->childs->next->inverted = 1;
					to_return->childs->next->subtree = pow;
					break;
			}
			//Now we can just return to_return. 
			tmp = canonicalize_tree(to_return);
			if(tmp == NULL){
				return NULL;
			}
			delete_tree(to_return);
			to_return = tmp;
			tmp = NULL;
			return to_return;
			break;

		case OPERATOR:
			/* We will have to switch by the operator type.
			 * PLUS is simple. Others are not that simple.
			 * (a^b)' == e^(b*ln(a))' == e^(b*ln(a))*(b'*ln(a)+b*a'/a) -- if a != 0;
			 * We can transform it to e^() and differentiate it then!
			 * More often than not, some of these a, b, a' and b' are zeros and ones.
			 * and multiplication is worst.
			 * What about creating separate function?*/
			switch(tree->symbol.oper){
				case PLUS:
					return diff_plus(tree->childs, variable);
					break;
				case POWER:
					return diff_power(tree->childs, variable);
					break;
				case MULTIPLY:
					return diff_multiply(tree->childs, variable);
					break;
			}
			break;
	}
	/*assert(false);*/
	return NULL;
}

Multitree * diff_plus(ListOfChilds * childs, char * variable){
	/*Deriving PLUS is quite simple. Just differentiate all childs and put them
	together.*/
	ListOfChilds * newchilds = NULL;
	Multitree * to_return;
	Multitree * diffed = NULL;
	Multitree * tmp;
	ListOfChilds * added;
	Number * zero;
	zero = construct_number();
	inttonum(zero, 0);
	while(childs != NULL){
		diffed = diff_tree(childs->subtree, variable);
		if (diffed == NULL){ /*something went wrong*/
			return NULL;
		}
		if ((diffed->symbol.type == NUMBER) && (numbercmp(diffed->symbol.number, zero) == 0)){
			childs = childs->next;
			delete_tree(diffed);
			diffed = NULL;
			continue;
		}
		added = give_me_empty_child();
		added->inverted = childs->inverted;
		added->subtree = diffed;
		added->next = newchilds;
		newchilds = added;
		childs = childs->next;
	}
	
	if(newchilds == NULL){
		to_return = inttotree(0);
	}else{
		if(newchilds->next == NULL){
			if(!(newchilds->inverted)){
				to_return = newchilds->subtree;
				GC_FREE(newchilds);
			}else{
				/*return 0-(newchilds)?*/
				to_return = give_me_empty_tree();
				to_return->symbol.type = OPERATOR;
				to_return->symbol.oper = PLUS;
				to_return->childs = give_me_empty_child();
				to_return->childs->inverted = 0;
				/*0*/
				to_return->childs->subtree = inttotree(0);
				to_return->childs->next = newchilds; /*We do not have to invert it, because it already is.*/
			}
		}else{
			/*We have enough childs to attach it to */
			to_return = give_me_empty_tree();
			to_return->childs = newchilds;
			to_return->symbol.type = OPERATOR;
			to_return->symbol.oper = PLUS;
		}
	}
	tmp = canonicalize_tree(to_return);
	if(tmp == NULL){
		return NULL;
	}
	delete_tree(to_return);
	to_return = tmp;
	tmp = NULL;
	return to_return;
}

size_t count_childs(ListOfChilds * childs){
	size_t number = 0;
	while(childs!= NULL){
		number = number + 1;
		childs = childs->next;
	}
	return number;
}


Multitree * diff_multiply(ListOfChilds * childs, char * variable){
	/*Derivative of a*b*c*... is sum a'*b*c*...+a*b'*c*...+a*b*c'*....+...
	Derivative of 1/b is -1*b'/b^2 (that needs a huge tree...)
	Derivation of multiplication is done in quadratic time :-)*/
	Multitree * diffed = NULL;
	ListOfChilds * for_multiplications = NULL;
	ListOfChilds * for_additions = NULL;
	Multitree * multiply = NULL; /*There will be multiplications connected*/
	Multitree * processing = NULL;
	ListOfChilds * added = NULL;
	Multitree * to_return = NULL;
	Multitree * pow = NULL;
	int minus;
	/*We can try to prune the tree during differentiation, but it seems to be quite difficult.
	Let the tree be simplyfied after it is differentiated.*/
	ListOfChilds * outer_pass = childs;
	ListOfChilds * inner_pass = childs;
	

	while (outer_pass != NULL){
		minus = 0;
		inner_pass = childs;
		//For every outer pass, we need to create new multiplication.
		for_multiplications = NULL;
		while(inner_pass != NULL){
			if(inner_pass != outer_pass){
				processing = copy_tree(inner_pass->subtree);
				added = give_me_empty_child();
				added->inverted = inner_pass->inverted;
				added->subtree = processing;
				added->next = for_multiplications;
				for_multiplications = added;
			}else{
				/*We can get here only once in one outer cycle. We should probably check it.
				TODO: Check how many times we get here in outer pass
				Now we need to diff. it. If it is not inverted, then just diff. it. Otherwise add more childs.*/
				if(inner_pass->inverted){
					/*1/a^2 to the for_multiplication and then add a' (it is comon for both inverted and not inverted)*/
					pow = give_me_empty_tree();
					pow->symbol.type = OPERATOR;
					pow->symbol.oper = POWER;
					pow->childs = give_me_empty_child();
					pow->childs->next = give_me_empty_child();
					pow->childs->next->next = NULL;
					/*Second child*/
					pow->childs->next->inverted = 0;
					pow->childs->next->subtree = inttotree(2);
					/*First child (copy of inner_pass->subtree).*/
					pow->childs->inverted = 0;
					pow->childs->subtree = copy_tree(inner_pass->subtree);
					/*pow is now a^2;*/
					/*added = new ListOfChilds;
					added->inverted = false;
					added->subtree = new Multitree;
					added->subtree->childs = NULL;
					added->subtree->symbol.type = NUMBER;
					added->subtree->symbol.number = -1;
					added->next = for_multiplications;
					for_multiplications = added;
					//We added -1;
					*/
					/*Why adding -1. We can just change inverted in additions.*/
					minus = 1;

					/*Now we add /a^2*/
					added = give_me_empty_child();
					added->inverted = 1;
					added->subtree = pow;
					added->next = for_multiplications;
					for_multiplications = added;
				}
				/*We add a' to for_multiplication (in all cases)*/
				processing = diff_tree(inner_pass->subtree, variable);
				if (processing == NULL){
					return NULL;
				}
				added = give_me_empty_child();
				added->inverted = 0;
				added->subtree = processing;
				added->next = for_multiplications;
				for_multiplications = added;
			}
			/*Advance inner loop;*/
			inner_pass = inner_pass->next;
		}
		/*We passed inner loop. Now we attach the result of it (for_multiplication) to the outer loop (for_addition)*/
		multiply = give_me_empty_tree();
		multiply->childs = for_multiplications;
		multiply->symbol.type = OPERATOR;
		multiply->symbol.oper = MULTIPLY;
		added = give_me_empty_child();
		added->subtree = multiply;
		added->inverted = minus;
		added->next = for_additions;
		for_additions = added;
		outer_pass = outer_pass->next;
	}
	diffed = give_me_empty_tree();
	diffed->symbol.type = OPERATOR;
	diffed->symbol.oper = PLUS;
	diffed->childs = for_additions;
	to_return = canonicalize_tree(diffed);
	if(to_return == NULL){
		return NULL;
	}
	delete_tree(diffed);
	return to_return;		
}


Multitree * diff_power(ListOfChilds * childs, char * variable){
	//(a^b)' == e^(b*ln(a))' == e^(b*ln(a))*(b'*ln(a)+b*a'/a) == a^b * (b'*ln(a) + b*a'/a) -- if a != 0;
	//And if a == 0? then just return 0.
	Multitree * to_return = NULL;
	Multitree * a=NULL;
	Multitree * b=NULL;
	Multitree * a_der=NULL;
	Multitree * b_der=NULL;
	Multitree * pow=NULL;
	Multitree * logarithm=NULL;
	Multitree * times1=NULL;
	Multitree * times2=NULL;
	Multitree * tmp=NULL;

	Number * zero;
	zero = construct_number();
	inttonum(zero, 0);
	if ((childs->subtree->symbol.type == NUMBER) && (numbercmp(childs->subtree->symbol.number, zero) == 0)){
		to_return = inttotree(0);
		return to_return;
	}

	/*Hope that at least something is zero.*/
	a = copy_tree(childs->subtree); /*Will be copied where needed.*/
	b = copy_tree(childs->next->subtree); /*Will be copied where needed.*/
	/*a and b should be deleted at the end of this function.*/
	b_der = diff_tree(b, variable);
	a_der = diff_tree(a, variable);
	if (a_der == NULL || b_der == NULL){
		return NULL;
	}
	//In any case, we need to create a^b part
	pow = give_me_empty_tree();
	pow->symbol.type = OPERATOR;
	pow->symbol.oper = POWER;
	pow->childs = give_me_empty_child();
	pow->childs->next = give_me_empty_child();
	pow->childs->next->next = NULL;
	pow->childs->next->inverted = 0;
	pow->childs->inverted = 0;
	pow->childs->subtree = copy_tree(a);
	pow->childs->next->subtree = copy_tree(b);
	/*a^b * (b'*ln(a) + b*a'/a)
	//We can now create the whole thing and then change it.
	//Or we can try to create only parts needed. But that means many ifs
	//Create the whole thing.*/
	logarithm = give_me_empty_tree();
	logarithm->symbol.type = FUNCTION;
	logarithm->symbol.func = LN;
	logarithm->childs = give_me_empty_child();
	logarithm->childs->next = NULL;
	logarithm->childs->inverted = 0;
	logarithm->childs->subtree = copy_tree(a);
	/*logarithm is complete.*/
	times1 = give_me_empty_tree();
	times1->symbol.type=OPERATOR;
	times1->symbol.oper = MULTIPLY;
	times1->childs = give_me_empty_child();
	times1->childs->next = give_me_empty_child();
	
	times1->childs->next->next = NULL;
	times1->childs->next->inverted = 0;
	times1->childs->next->subtree = logarithm;
	
	times1->childs->inverted = 0;
	times1->childs->subtree = copy_tree(b_der);
	/*times1 is complete*/
	times2 = give_me_empty_tree();
	times2->symbol.type = OPERATOR;
	times2->symbol.oper = MULTIPLY;
	/*three childs.*/
	times2->childs = give_me_empty_child();
	times2->childs->next = give_me_empty_child();
	times2->childs->next->next = give_me_empty_child();
	/*last*/
	times2->childs->next->next->next = NULL;
	times2->childs->next->next->inverted = 1;
	times2->childs->next->next->subtree = copy_tree(a);
	/*center*/
	times2->childs->next->inverted = 0;
	times2->childs->next->subtree = copy_tree(a_der);
	/*first*/
	times2->childs->inverted = 0;
	times2->childs->subtree = copy_tree(b);
	/*plus*/
	Multitree * plus = give_me_empty_tree();
	plus->symbol.type = OPERATOR;
	plus->symbol.oper = PLUS;
	plus->childs = give_me_empty_child();
	plus->childs->next = give_me_empty_child();
	plus->childs->next->next = NULL;
	plus->childs->inverted = 0;
	plus->childs->next->inverted = 0;
	plus->childs->next->subtree = times2;
	plus->childs->subtree = times1;
	/*plus is complete. Now connect it with pow with Multiplication and we are ready to return it.*/
	to_return = give_me_empty_tree();
	to_return->symbol.type = OPERATOR;
	to_return->symbol.oper = MULTIPLY;
	/*two childs. first is pow, second is plus.*/
	to_return->childs = give_me_empty_child();
	to_return->childs->next = give_me_empty_child();
	/*second*/
	to_return->childs->next->next = NULL;
	to_return->childs->next->inverted = 0;
	to_return->childs->next->subtree = plus;
	to_return->childs->inverted = 0;
	to_return->childs->subtree = pow;
	/*Finished.*/
	delete_tree(a);
	delete_tree(b);
	delete_tree(a_der);
	delete_tree(b_der);
	tmp = canonicalize_tree(to_return);
	if(tmp == NULL){
		return NULL;
	}
	delete_tree(to_return);
	to_return = tmp;
	tmp = NULL;
	return to_return;
}
